Экзаменационный билет №1

1. Структуры данных и математические модели.

Одной из наиболее общих математических абстракций является понятие алгебраической системы < А, О, R >, где

Если операций нет - модель (структура). Если отношений нет - универсальная алгебра.

Математическая структура S=(M1,…,Mk; p1,…,ps) есть одно или несколько множеств М1,…,Мк, элементы которых находятся в некоторых отношениях р1,…,ps.

Структура данных - модель данных в виде математической структуры.

Примеры:

2. Разработка общего представления линейного списка для обеспечения списковой структуры хранения.

Значения представлены в виде объектов классов, являющихся производными из одного общего базового класса.

В поле значения звена списка размещается указатель на объект значение.

Для повышения общности схемы реализации будем использовать вместо величины NULL константу pStop для фиксации ситуаций, в которых указатель не содержит адрес какого-либо звена списка.

Информационные методы:

Методы доступа к значениям в списке:

Методы навигации по списку (итератор):

Вставка звеньев:

Удаление звеньев:

Экзаменационный билет №2

1. Понятие экземпляра и схемы структуры на примере стека. Элементы базисного множества динамической структуры стек.

Схема стуктуры - структура данных Sa = (Ма, R; pa, p1), соответствующая рассмотрению структуры как переменной величины.

Алгоритм соответствует схеме структуры

Экземпляр - структура данных Sa ^ * = (Ма, R; pa, p1 ^ *) с установленными значениями элементов.

Вычисление соответствует экземпляру

Структуры с бинарными отношениями допускают случай графического изображения

2. Плекс, как представление арифметического выражения.

Плекс - структура представления для выражений самого общего вида (линия – операция, точки – операнды)

Пример:

Экзаменационный билет №3

1. Динамические структуры: свойства и применение.

Структуры данных являются операндами операций обработки.

Результаты вычислений также являются структурами, модель которых может как совпадать, так и отличаться от структуры исходных данных.

Пример. Организация последовательного вызова подпрограмм.

Анализ примера:

Динамическая структура - математическая структура, которой соответствует частично-упорядоченное (по включению) базовое множество M, элементы которого являются структурами данных. При этом отношения включения индуцируются операциями преобразования структуры данных.

Примеры:

Средства поддержки динамической структуры - программы реализующие отношения включения

Взято из интернета

Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости.

Свойства:

Выгодно использовать, если:

Может быть эта схема здесь не нужна

2. Реализация списка на языке программирования высокого уровня.

Подход 1

Для имитации звеньев могут быть использованы два массива один из которых используется для хранения значений, другой- для хранения индексов следующих элементов. В этом случае, звено есть элемент массивов с одинаковым индексом, адрес (имя) звена – индекс массивов.

Подход 2

С использованием ООП звено может быть представлено в виде объекта. Образ памяти, выделенной для хранения структур данных, в это случае будет представлять массив звеньев-объектов.

Class TLink
{
 Public:
    Intvalue;//значение
    Intnext;//индекс следующего звена
 Protected:
    TLink();
};
TLinkMem[MemLimit];

Экзаменационный билет №4

1. Реализация множества как набора номеров элементов универса. Оценка сложности по памяти. Оценка сложности по времени.

Множество – набор элементов

Операции над множествами

int TBitField::GetBit(const int n) const
{
    if ((n > -1) && (n < BitLen))
        return (pMem[(GetMemIndex(n))] & (GetMemMask(n)));
    else return(0);
}
void TBitField::SetBit(const int n)
{   if ((n > -1) && (n < BitLen))
        pMem[(GetMemIndex(n))] |= GetMemMask(n);
}
void TBitField::ClrBit(const int n)
{   if ((n > -1) && (n < BitLen))
        pMem[(GetMemIndex(n))] &= ~GetMemMask(n);
}

Теоретико-множественные операции

TBitField TBitField::operator|(const TBitField& bf)
{
    int i, len;
    if (BitLen > bf.BitLen)
        len = BitLen;
    else len = bf.BitLen;
    TBitField temp(len);
    for (i = 0; i < MemLen; i++)
        temp.pMem[i] = pMem[i];
    for (i = 0; i < bf.MemLen; i++)
        temp.pMem[i] |= bf.pMem[i];
    return temp;
}
TBitField TBitField::operator&(const TBitField &bf)
{
    int i, len;
    if (BitLen < bf.BitLen)
        len = BitLen;
    else len = bf.BitLen;
    TBitField temp(len);
    for (i = 0; i < MemLen; i++)
        temp.pMem[i] = pMem[i];
    for (i = 0; i < bf.MemLen; i++)
        temp.pMem[i] &= bf.pMem[i];
    return temp;
}
TBitField TBitField::operator~(void)
{
    TBitField temp(BitLen);
    for (int i = 0; i < MemLen; i++)
        temp.pMem[i] = ~pMem[i];
    return temp;
}

Универс U – множество всех элементов.

Конкретизация (допущения и ограничения):

Оценка сложности по времени

Битовое поле представляет из себя массив int

Бред, который нужно исправить:

Оценка сложности по памяти

Бред, который нужно исправить:

2. Линейный список как динамическая структура. Базисное множество. Неоднозначность операций вставки и удаления.

Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.

Среда выполнения обеспечивает динамически–распределяемую область памяти:

Базисное множество - структуры

Неоднозначность операций в том что можем вставлять как в голову так и в хвост и после текущего и удалять можно тоже по-разному.

Для показа неоднозначности взять простой односвязный линейный список с головой и двусвязный с хвостом и головой.

Экзаменационный билет №5

1. Представление множества битовой строкой. Оценки сложности по памяти и времени.

ВОЗМОЖНО ПО ТЕМЕ

Множество – набор элементов. Для множества определены операции: проверка наличия элемента aA, добавление элемента A+a, удаление элемента A –a. Теоретико-множественные операции: объединение AB, пересечение AB, вычитание A. Универс U – множество всех элементов. Конкретизация (допущения и ограничения): элементы множества проиндексированы (каждому элементу соответствует уникальный индекс), множество индексов элементов составляют непрерывный диапазон целых значений. Тогда любое множество AU может быть описано характеристическим вектором =(1 2… n), , если иначе. Множество → битовая строка → массив битовых элементов → оперативная память (обратный порядок хранения). Нумерация бит в битовой строке – слева направо. Нумерация элементов в массиве – слева направо, биты элемента – справа налево. Байты двухбайтового элемента располагаются в ОП в обратном порядке (сначала байт с младшими битами, затем байт со старшими битами).

2. Реализация стека с использованием динамически распределяемой памяти.

Вставка в стек

    PTDatLink pTemp;
    pTemp = new TDatLink();
    pTemp-> SetDatValue(Val);
    pTemp->SetNextLink(pFirst);
    pFirst = pTemp;

Выборка из стека

    PTDatLink pTemp = pFirst;
    Val = pFirst->GetDatValue();
    pFirst = pFirst->GetNextLink();
    delete pTemp;

Экзаменационный билет № 6

1. Управление памятью путем перепаковки структур хранения на прмере реализации N стеков на одном массиве.

Перепаковка памяти (перепаковка) - процедура динамического перераспределения памяти путем переписи части хранимых значений в другую область

Перепаковка обеспечивает эффективное использование одного ресурса ЭВМ (памяти) за счет другого ресурса (времени).

Для выполнения перепаковки требуется разработка управляющих программ.

Управление памятью - выполнение функций анализа свободной памяти, планирование размещения структур, переписывание структур

Система управления памятью - комплекс программ, реализующих управление памятью

Необходимость перепаковки обуславливается принятым способом реализации отношений следования.

Свойства:

Выполняется при попытке вставки нового значения в стек s, у которого отсутствует свободная память: F = 'сумма' (Hik-Lik-1-1), 1 <= k <= N.

Для гарантированного выделения свободной памяти стеку s при наличии только одного свободного элемента памяти (случай 2), выполним:

2. Структуры хранения для матриц специального вида

Ленточные матрицы

Для хранения элементов можно выделить непрерывный вектор памяти размера 3n-2 Адрес (aij) = a(альфа) + 3(i-1) + (j-i)

Треугольные матрицы

Подход 1:

Подход 2:

Подход 3:

Подход 4:

Экзаменационный билет №7

1. Матрица как вектор векторов и матрица как вектор указателей. Оценки сложности по памяти и времени.

Бред, который нужно исправить

Оценки сложности по памяти

это же треугольные матрицы, в матрице рамером n * n n ^ 2 ячееки, нулевые мы не храним

Оценки сложности по времени

поиск будет О(1)т.к. мы просто индекс считаем грубо говоря,если с матрицами типо A + B,где а и б матрицы, то нам нужно каждый элемент с каждым сложитьсоотв. это будет такой же O как и у памятивычитание аналогично а как скалярное произведение матриц-сумма попарных произведений?

2. Статическое и динамическое распределение памяти.

Статическое распределение памяти - распределение памяти до начала процесса вычислений.

Динамическое распределение памяти - распределение памяти в ходе выполнения программы.

Перепаковка памяти (перепаковка) - процедура динамического перераспределения памяти путем переписи части хранимых значений в другую область памяти.

Экзаменационный билет №8

1. Роль гипотез о росте структур при разработке систем управления памятью путем перепаковки на примере работы с N стеками.

Гипотезы о поведении структур служат основой для принятия решений о распределении памяти.

Формирование гипотез происходит в результате теоретического анализа модели решаемой задачи или может быть выполнено на основе статистических данных, получаемых в ходе вычислительных экспериментов с проектируемой программной системой.

Гипотеза 1: Стеки используются с одинаковой интенсивностью, память разделяется между стеками поровну.

Гипотеза 2: Интенсивность использования стеков различается.

Li'k = Li'k-1 + (Hik-1 - Lik-1 + 1) + F * ((дельта, похожая на б итая) / (дельта в виде треугольника)),  1 < k < N

Гипотеза 3: Использование вероятностных предположений о поведении стеков.

Li'k = Li'k-1 + (Hik-1 - Lik-1 + 1) + (1-тета) * (F / N) + тета * F * ((дельта, похожая на б итая) / (дельта в виде треугольника)),  1 < k < N.

2. Структура хранения множеств.

Множество – набор элементов

Операции над множествами

int TBitField::GetBit(const int n) const
{
    if ((n > -1) && (n < BitLen))
        return (pMem[(GetMemIndex(n))] & (GetMemMask(n)));
    else return(0);
}
void TBitField::SetBit(const int n)
{   if ((n > -1) && (n < BitLen))
        pMem[(GetMemIndex(n))] |= GetMemMask(n);
}
void TBitField::ClrBit(const int n)
{   if ((n > -1) && (n < BitLen))
        pMem[(GetMemIndex(n))] &= ~GetMemMask(n);
}

Теоретико-множественные операции

TBitField TBitField::operator|(const TBitField& bf)
{   int i, len;
    if (BitLen > bf.BitLen)
        len = BitLen;
    else len = bf.BitLen;
    TBitField temp(len);
    for (i = 0; i < MemLen; i++)
        temp.pMem[i] = pMem[i];
    for (i = 0; i < bf.MemLen; i++)
        temp.pMem[i] |= bf.pMem[i];
    return temp;
}
TBitField TBitField::operator&(const TBitField& bf)
{
    int i, len;
    if (BitLen < bf.BitLen)
        len = BitLen;
    else len = bf.BitLen;
    TBitField temp(len);
    for (i = 0; i < MemLen; i++)
        temp.pMem[i] = pMem[i];
    for (i = 0; i < bf.MemLen; i++)
        temp.pMem[i] &= bf.pMem[i];
    return temp;
}
TBitField TBitField::operator~(void)
{   TBitField temp(BitLen);
    for (int i = 0; i < MemLen; i++)
        temp.pMem[i] = ~pMem[i];
    return temp;
}

Универс U – множество всех элементов

Экзаменационный билет №9

1. Управление свободной памятью при использовании сцепления.

ОБЩАЯ ИНФОРМАЦИЯ О СЦЕПЛЕНИЯХ

Способ задания отношения следования, в котором фиксация месторасположения следующего элемента производится путем запоминания соответствующего адреса памяти, называется сцеплением (пары, хранящие ai и ai+1, сцеплены адресными указателями). Для изображения структуры хранения с использованием сцепления звенья памяти рисуются в виде прямоугольников, а сцепление звеньев показывается в виде стрелок. Индикация последнего звена в списке обычно производится записью в поле адреса некоторого барьера – фиктивного (неадресного) значения (как правило, 0 или -1). Для доступа к звеньям списка должен быть известен адрес первого звена списка. Указатель, в котором этот адрес запоминается, называется переменной связи. Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.

2. Алгоритм сложения многочленов от N переменных.

Основные алгоритмические моменты метода сложения полиномов operator+ состоят в следующем:

TList TList::plus(TList list)
{
    pLink tmp, ptr, temp, prev1, prev2, cnt, n;
    tmp = prev1 = cnt = Head;
    ptr = prev2 = temp = n = list.Head;
    size = this->GetSize();
    int flag = 1;
    while ((tmp->pNext->data != -1) && (ptr->pNext->data != -1))
    {
        if ((ptr->data == -1) && (tmp->data == -1))
        {
            ptr = ptr->pNext;
            tmp = tmp->pNext;
            temp = temp->pNext;
            cnt = cnt->pNext;
        }
        if ((tmp->data > ptr->data) && (flag == 1))
        {
            ptr = ptr->pNext;
            this->insCurrent(temp->data, temp->data2);
            list.deleteCurrent(temp->data);
            temp = ptr;
            flag = 0;
        }
        if ((tmp->data < ptr->data) && (flag == 1))
        {
            ptr = ptr->pNext;
            tmp = tmp->pNext;
            this->insCurrent(temp->data, temp->data2);
            list.deleteCurrent(temp->data);
            temp = ptr;
            flag = 0;
        }
        if ((tmp->data == ptr->data) && (flag == 1))
        {
            this->insCurrent(tmp->data, tmp->data2 + ptr->data2);
            if ((tmp->data2 + ptr->data2) == 0)
            {
                while ((prev1->pNext != tmp) && (n->pNext != ptr))
                {
                    prev1 = prev1->pNext;
                    n = n->pNext;
                }
                tmp = tmp->pNext;
                ptr = ptr->pNext;
                this->deleteCurrent(cnt->data);
                list.deleteCurrent(temp->data);
                cnt = tmp;
                temp = ptr;
            }
            flag = 0;
        }
        flag = 1;
    }
    if ((ptr->data == tmp->data) && (ptr->data != -1) && (tmp->data != -1))
    {
        this->insCurrent(ptr->data, tmp->data2 + ptr->data2);
        if ((tmp->data2 + ptr->data2) == 0)
        {
            while ((prev1->pNext != tmp) && (n->pNext != ptr))
            {
                prev1 = prev1->pNext;
                n = n->pNext;
            }
            tmp = tmp->pNext;
            ptr = ptr->pNext;
            this->deleteCurrent(cnt->data);
            list.deleteCurrent(temp->data);
            list.size--;
            cnt = tmp;
            temp = ptr;
        }
    }
    if (ptr->data != tmp->data)
    {
        if (tmp->data == -1)
            while (ptr->pNext != list.Head)
            {
                this->insCurrent(ptr->data, ptr->data2);
                ptr = ptr->pNext;
                list.size--;
            }
    }
    if ((ptr->data != -1) && (tmp->data != -1))
    {
        this->insCurrent(ptr->data, ptr->data2);
        list.deleteCurrent(ptr->data);
    }

    return *this;
}

Экзаменационный билет №10

1. Общая характеристика стандартной библиотеки шаблонов.

В стандарте языка С++ предусматривается наличие в среде программирования стандартной библиотеки шаблонов (Standard Template Library, STL).

Основные понятия библиотеки STL.

Библиотека включает в свой состав большое количество контейнеров, представляющих собой структуры данных, в которых могут храниться объекты.

В числе имеющихся контейнеров:

Для быстрого и эффективного построения вычислительных процедур, библиотека обеспечивает итераторы для всех видов контейнеров, которые представляют унифицированный механизм последовательного доступа к элементам контейнеров.

Общая схема:

В зависимости от типа контейнера, итератор может обеспечивать прямой доступ, быть одно- или дву- направленным, предназначенным только для чтения или записи и др. Библиотека содержит для контейнеров большое количество реализованных обобщенных алгоритмов.

В числе таких алгоритмов:

2. Алгоритм обхода иерархического списка (итератор).

Печать текста: схема обхода

while (1)
{
   if ( pLink != NULL )
   {
       cout << pLink->Str; // обработка звена
       St.push(pLink); // запись в стек
       pLink = pLink->pDown; // переход на подуровень
   }
   else if ( St.empty() )
       break;
   else
   {
       pLink = St.top();
       St.pop(); // выборка из стека
       pLink = pLink->pNext; // переход по тому же уровню
   }
}

Ввод текста из файла: уровень текста в файле можно выделить строками специального вида (например, скобками '{' и '}').

Общая схема алгоритма:

повторить:
ввод строки
ЕСЛИ '}' ТО Завершить
ЕСЛИ '{' ТО Выполнить рекурсивно Ввод_текста
Добавить строку на том же уровне

Экзаменационный билет №11

1.Представление многочленов от N переменных. Исключение хранения мономов с нулевыми коэффициентами

2. Копирование текста.

Для копирования текста необходимо предварительно скопировать разделы текста, на которые указывают указатели pDown и pNext

Алгоритмы обхода NDT или DNT.

Каждое звено текста копируется за два прохода:

Экзаменационный билет №12

1.Сборка мусора (Повторное использование памяти).

При удалении разделов текста для освобождения звеньев следует учитывать следующие моменты:

Память, занимаемая удаляемым текстом, не освобождается, а удаление текста фиксируется установкой указателей в состояние NULL (например, pFirst=NULL).

Возможный подход доступа к системе управления памятью – разработка специальной системы управления при помощи перегрузки операторов new и delete.

Общая схема подхода

class TTextMem{
    PTTextLink pFirst; // первое звено
    PTTextLink pLast; // последнее звено
    PTTextLink pFree; // первое свободное
void TTextLink::InitMemSystem(int size) // инициализация памяти
{
    char Line[100];
    char *tmp = new char[sizeof(TTextLink)*size];
    MemHeader.pFirst = (PTTextLink)new char[sizeof(TTextLink)*size];
    MemHeader.pFree = MemHeader.pFirst;
    MemHeader.pLast = (PTTextLink)tmp + size - 1;
    PTTextLink pLink = MemHeader.pFirst;
    for (int i = 0; i < size - 1; i++, pLink++) // размер памяти
        pLink->pNext = pLink + 1;
    pLink->pNext = nullptr;
}
void * TTextLink::operator new(size_t size) // выделение звена
{
    PTTextLink pLink = MemHeader.pFree;
    if (MemHeader.pFree != nullptr)
        MemHeader.pFree = pLink->pNext;
    return pLink;
}
void operator delete (void *pM)
{
    PTTTextLink pLink=(PTTTextLink)pM;
    pLink->pNext=MemHeader.pFree;
    MemHeader.pFree=pLink;
}

2. Оценка сложности обработки деревьев поиска.

Тmin=1
Tmax=log2N(при сбалансированном дереве)
Tmax=N(при вырожденном дереве)

Экзаменационный билет №13

1.Представление текста связным списком.

Текст – линейная последовательность символов

Текст – линейная последовательность слов (слово - линейная последовательность символов)

Текст – линейная последовательность строк, строки состоят из слов, слова – из символов и т.д.

Математическая модель текста – иерархическая структура представления (дерево).

Единый тип звена:

typedef Tlink *PTLink;
class TLink
{
    PTLink pNext;
    int Atom; // =1 – звено-атом
    union {PTLink pDown; char Symb;}

2. Таблицы с вычислимым входом.

Таблица с вычисляемым входом (хеш-таблица) – это таблица, элементы которой располагаются в соответствии с некоторой функцией расстановки (хеш-функцией)

Функция расстановки f (ключ) вычисляет для каждого элемента таблицы по его ключу номер (позицию) элемента в массиве.

Метод цепочек.

Замечания к открытому перемешиванию как способу размешения коллизий:

Широко используемый подход для разрешения коллизий - метод цепочек, когда все записи, для которых функция хеширования определяет одно и тоже значение,представляются в виде линейного списка.

Открытое перемешивание еще называют закрытым хэшированием, метод цепочек - открытое хэширование.

Экзаменационный билет №14

1.Алгоритм обхода иерархического списка (итератор).

Печать текста: схема обхода

while (1)
{
   if ( pLink != NULL )
   {
       cout << pLink->Str; // обработка звена
       St.push(pLink); // запись в стек
       pLink = pLink->pDown; // переход на подуровень
   }
   else if ( St.empty() )
       break;
   else
   {
       pLink = St.top();
       St.pop(); // выборка из стека
       pLink = pLink->pNext; // переход по тому же уровню
   }
}

Ввод текста из файла: уровень текста в файле можно выделить строками специального вида (например, скобками '{' и '}')

Общая схема алгоритма:

повторить:
ввод строки
ЕСЛИ '}' ТО Завершить
ЕСЛИ '{' ТО Выполнить рекурсивно Ввод_текста
Добавить строку на том же уровне

Реализация итератор:

int TText::Reset(void) // Установка на корневое звено текста
{
   pCurrent = pFirst;
   if (pCurrent != nullptr)
   {
       St.push(pCurrent);
       if (pCurrent->pNext != nullptr)
           St.push(pCurrent->pNext);
       if (pCurrent->pDown != nullptr)
           St.push(pCurrent->pDown);
   }
}

bool TText::IsTextEnded(void) const // Стек пуст?
{
   return St.empty();
}

bool TText::GoNext(void) // Переход к следующему звену текста
{
   if (!IsTextEnded())
   {
       pCurrent = St.top();
       St.pop();
       if (pCurrent != pFirst)
       {
           if (pCurrent->pNext != nullptr)
               St.push(pCurrent->pNext);
           if (pCurrent->pDown != nullptr)
               St.push(pCurrent->pDown);
       }

   }
   return IsTextEnded();
}

2. Пример использования стеков: преобразование арифметических выражений в польскую форму записи.

Формат записи выражения.

Алгоритм:

  1. Для операций вводится приоритет:'*' '/' (3), '+' '-' (2), '(' (1), '=' (0),
  2. Для хранения данных используется 2 стека (1 – для результата, 2 – для операций),
  3. Исходное выражение просматривается слева направо,
  4. Операнды по мере их появления помещаются в стек 1 ,
  5. Символы операций и левые скобки помещаются в стек 2,
  6. При появлении правой скобки последовательно изымаются элементы из стека 2 и переносятся в стек 1. Данные действия продолжаются либо до опустошения стека 2 либо до попадания в стеке 2 на левую скобку,
  7. Если текущая операция, выделенная при обходе выражения, имеет меньший (более низкий) приоритет, чем операция на вершине стека 2, то такие операции из стека 2 переписываются в стек 1.

Экзаменационный билет №15

1.Изменение структуры текста (вставка и удаление строк)

void TText::DelDownLine(void) // Удаление строки в подуровне
{
   if (pCurrent == nullptr)
       SetRetCode(TextErr);
   else if (pCurrent->pDown == nullptr)
       SetRetCode(TextNoDown);
   else if (pCurrent->pDown->IsAtom())
       pCurrent->pDown = pCurrent->pDown->pNext;
}

void TText::InsDownLine(string str) // Вставка строки в подуровень
{
   if (pCurrent == nullptr)
       SetRetCode(TextErr);
   else
   {
       TStr buf; // typedef char TStr[TextLineLength];
       strcpy(buf, str.c_str());
       pCurrent->pDown = new TTextLink(buf, pCurrent->pDown, nullptr);
   }
}

2. Деревья поиска. Алгоритм удаления.

void TTreeTable :: DelRecord ( TKey k ) { // удалить запись
  if ( FindRecord(k) == NULL ) SetRetCode(TabNoRec); // SKIP_ON
  else {
    SetRetCode(TabOK);
    PTTreeNode pNode = *ppRef;
    if ( pNode->pRight == NULL ) *ppRef = pNode->pLeft; // один потомок слева
    else if ( pNode->pLeft == NULL ) *ppRef = pNode->pRight; // один потомок справа
    else { // два потомка - поиск крайнего справа у левого поддерева
      PTTreeNode pN = pNode->pLeft, *ppR = &pNode->pLeft;
      while ( pN->pRight != NULL ) {
        ppR = &pN->pRight; pN  = *ppR;
      } // вместо удаления pNode удается pN
      pNode->pValue = pN->pValue;   // значение в pNode
      pNode->Key    = pN->Key;
      pNode = pN; *ppR = pN->pLeft; // обход удаляемого pN
    }
    delete pNode;
  }                                                    // SKIP_OFF
}

Экзаменационный билет №16

1.Адаптивная оценка параметров модели в ходе выполнения программ (на примере системы управления несколькими стеками).

2. Оценка сложности обработки деревьев поиска. Понятие сбалансированных и идеально сбалансированных деревьев поиска.

Дерево является идеально сбалансированным если для каждого его узла количество узлов в левом и правом поддеревьях различаются не более чем на 1. Дерево является сбалансированным,если для каждого узла высота левого и правого поддеревьев различаются не более,чем на 1(АВЛ-деревья). Идеально сбалансированные деревья являются сбалансированными.Операции обработки сбалансированных деревьев имеют сложность log2N.(поиск,вставка,удаление) Тmin=1 Tmax=log2N(при сбалансированном дереве) Tmax=N(при вырожденном дереве)

Экзаменационный билет №17-18

1.Организация доступа по имени.

Структура памяти

Структура данных

Возможные задания f:возможный способ-табличное задание функции:

  1. Таблица-последовательность строк(записей)
  2. Запись может состоять из нескольких полей
  3. Одно из полей должно задавать имя записи(ключ),остальные поля образуют тело записи.

Операции под таблицей:

Таблица - динамическая структура данных.

Базисное множество - семейство линейных структур из записей, базисное отношение включения определяется операциями вставки и удаления записей.

Варианты расширения понятия таблицы:

Принцип реализации таблиц:

Введение различных способов предполагает явное или неявное существование разных типов ситуаций при использовании таблиц.

Просматриваемые таблицы.

Таблица последовательности строк(записей)

По организации способа доступа таблицы делятся на следующие категории:

В просматриваемой таблице порядок расположения элементов никак не связан со значениями ключей (рис. II-34). Поэтому поиск элемента по ключу осуществляется обычным просмотром всех элементов таблицы, начиная с первого и до искомого

Ключ Информация
08 ...
33 ...
47 ...
25 ...
18 ...

рис. II-34

Таким образом, при удалении элемента надо:

Поскольку операция поиска возвращает искомый элемент и не сообщает о месте его размещения в списке, при реализации операции удаления элемента из списка приходится либо

Алгоритм удаления элемента из просматриваемой таблицы-списка по варианту a) приведен на рис. II–39.

Ниже приводится текст программы, соответствующий приведенному алгоритму.

struct Item
{
    int key;
    Type info;
    Item *next;
};
Item *ptab; /*указатель на начало таблицы */
int del1(int k)
{
    Item *cur, *prev;
    cur = ptab;
/*проверяем, есть ли в таблице элементы */
    if(!cur)
        return -1; /*таблица пуста – отказ */
/*возможно, требуется удалить первый элемент таблицы */
    if(cur->key == k)
    {
    /* удаляем первый элемент */
        ptab = cur->next;
        delInfo(cur->info);
        delete cur;
        return 0;
    }
/* ищем удаляемый элемент среди других элементов таблицы */
    while(cur->next)
    {
    /* есть другие элементы */
        prev = cur;
        cur = cur->next;
        if(cur->key == k)
        {
        /* нашли элемент, который надо удалить */
            prev->next = cur->next;
            delInfo(cur->info);
            delete cur;
            return 0;
        }
    }
/* естественный выход из цикла – в таблице нет элемента с ключом k */
    return -1;
}

2. Роль гипотез о росте структур при разработке систем управления памятью путем перепаковки.

Дерево является идеально сбалансированным если для каждого его узла количество узлов в левом и правом поддеревьях различаются не более чем на 1. Дерево является сбалансированным,если для каждого узла высота левого и правого поддеревьев различаются не более,чем на 1(АВЛ-деревья). Идеально сбалансированные деревья являются сбалансированными.Операции обработки сбалансированных деревьев имеют сложность log2N.(поиск,вставка,удаление) Тmin=1 Tmax=log2N(при сбалансированном дереве) Tmax=N(при вырожденном дереве)

Экзаменационный билет №19

1.Упорядоченные таблицы. Алгоритм быстрой сортировки.

Сортированные (упорядоченные) таблицы - таблицы, в которых записи располагаются в порядке возрастания (или убывания) ключей

Упорядоченность таблиц может быть организована только при возможности сравнения ключей (на множестве ключей задано отношение линейного порядка).

Сортировка - действия, связанные с размещением записей в порядке возрастания (или убывания) ключей

Алгоритм сортировки называют устойчивым, если он никогда не меняет относительный порядок в таблице двух записей с равными ключами

Внутренняя сортировка - Упорядочивание данных, при котором все значения располагаются в ОП

Сортировка включением

Идея похода – вставка нового значения в упорядоченный набор данных.

Алгоритм быстрой сортировки.

Идея подхода (Hoare C.A.R.)– использование процедуры разделения упорядочиваемого набора на две части, в одной из которых располагаются значения, меньшие некоторого порогового (ведущего) элемента массива, в другой – соответственно большие значения. Подобный способ разделения может быть выполнен без привлечения дополнительной памяти.

При наличии процедуры разделения алгоритм сортировки может быть определен рекурсивно – необходимо разбить упорядочиваемый набор на два блока с меньшими и большими значениями соответственно и затем последовательно отсортировать полученные блоки.

2. Реализация структуры хранения нескольких стеков с использованием списков на языке высокого уровня

Все свободные звенья объединяются в один список свободных звеньев. Звенья этого списка используются при необходимости свободной памяти, в этот список звенья должны возвращаться после освобождения.

Схемы работы со стеком и со списком свободных звеньев совпадают. Список свободных звеньев есть стек.

Экзаменационный билет №20

1.Деревья поиска как способ организации таблицы. Алгоритмы обхода.

Дерево - связный граф без циклов

Структура типа дерева (древовидная структура) с базовым типом T

Дерево поиска - деревоб в котором для любой вершины бинарного дерева значения в левом потомке меньше значения узла, а значение в правом потомке больше значения узла

Обработка дерева – выполнение необходимой операции для каждой узла дерева. Реализация подобного типа действий предполагает умение обхода (обхода) дерева

2. Сравнение непрерывной и списковой структур хранения.

Непрерывная память Списки
Перепаковка для динамического распределения памяти Динамическое распределение памяти эффективно реализуется при помощи списка свободных звеньев
В структуре хранения хранятся только данные В структуре хранения хранятся данные и указатели
К элементам структуры данных обеспечивается К элементам структуры данных обеспечивается
Прямой доступ Последовательный доступ

Экзаменационный билет №21

1.Плексы как представление рисунков, состоящих из точек и соединяющих их отрезков.

Рассмотрим в качестве базовых объектов основные геометрические фигуры – точку, окружность, прямоугольник и т.д.

Информационное описание объектов – параметры фигуры (координаты, размер, радиус и др.). В общем случае, описание фигуры включает значение координат некоторой опорной точки.

Операции обработки геометрических объектов включают методы для задания и изменения параметров; расширим набор операций процедурами визуализации (например, на экране дисплея) и скрытия фигур.

Для обеспечения возможности динамической визуализации геометрических объектов введем тип данных, значения которого вычисляются в соответствии с задаваемым формульным выражением.

Составной объект – набор геометрических объектов (как базовых, так и составных), рассматриваемых при выполнении операций обработки как единый объект.

Геометрический объект может быть сконструирован с использованием уже существующих объектов (например, ломаная может быть определена через набор конечных точек составляющих отрезков).

Геометрический объект может быть образован при помощи сборки существующих объектов – рассмотрим данный способ построения новых объектов на примере рисунков (чертежей), образованных только из объектов двух базовых типов: точек и линий

2. Сравнение непрерывной и списковой структур хранения.

#define MemSize 25 // размер памяти для стека
class TStack
{
 protected:
    int Mem[MemSize]; // память для СД
    int Top; // индекс последней занятой ячейки
 public:
    TStack () { Top = -1; }
    int IsEmpty (void) const { Top == -1; }
    int IsFull (void) const { Top == MemSize-1;}
    void Put ( const int Val ) { Mem[++Top] = val; }
    TData Get (void) { return Mem[Top--]; }
};

Очередь

Способы достижения полного использования памяти:

Сдвиг значений очереди после выборки очередного значения (т.е. обеспечение Li=0) – возрастание накладных расходов, использование левого участка свободной области при достижении Hi=n-1 (т.е. при отсутствии свободной памяти справа).

Циклический или кольцевой буфер - структура хранения, получаемая из вектора расширением отношения следования парой p(an,a1). Реализация кольцевого буфера логически может быть обеспечена переходом индексов Li и Hi при достижении граничного значения MemSize-1 на индекс первого элемента вектора памяти.

Экзаменационный билет №22-23

1. Способы агрегации графических объектов (группирование и конструирование).

Агрегация – это абстракция, которая превращает связь между объектами в некоторый агрегированный объект.

Группирование

Составной объект - набор геометрических объектов (как базовых так и составных), рассматриваемых при выполнении операций обработки как единый объект

class TChartGroup : public TChartRoot
{
 protected:
    TDatList Group;  // Список объектов
 public:
    TChartGroup() { }
    void InsUnit(TChartRoot *pUnit);  // Добавление
    virtual void Show();  // Визуализация
    virtual void Hide();  // Скрытие
    virtual void CalcParams(double t = -1);  // Пересчет параметров
};

Конструирование

Геометрический объект может быть сконструирован с использованием уже существующих объектов

class TChartPolyline : public TChartGroup
{
 public:
    TChartPolyline() { }
    void InsPoint(TChartRoot *pUnit);  // Добавление
    virtual void Show();  // Визуализация
    virtual void Hide();  // Скрытие
    virtual void CalcParams(double t = -1);  // Пересчет параметров
};

2. Сравнение структур хранения линейных и динамических структур данных.

Линейные структуры

Динамические структуры

Экзаменационный билет №22

1. Способы агрегации графических объектов (группирование и конструирование).

Агрегация – это абстракция, которая превращает связь между объектами в некоторый агрегированный объект.

Группирование

Составной объект - набор геометрических объектов (как базовых так и составных), рассматриваемых при выполнении операций обработки как единый объект

class TChartGroup : public TChartRoot
{
 protected:
    TDatList Group;  // Список объектов
 public:
    TChartGroup() { }
    void InsUnit(TChartRoot *pUnit);  // Добавление
    virtual void Show();  // Визуализация
    virtual void Hide();  // Скрытие
    virtual void CalcParams(double t = -1);  // Пересчет параметров
};

Конструирование

Геометрический объект может быть сконструирован с использованием уже существующих объектов

class TChartPolyline : public TChartGroup
{
 public:
    TChartPolyline() { }
    void InsPoint(TChartRoot *pUnit);  // Добавление
    virtual void Show();  // Визуализация
    virtual void Hide();  // Скрытие
    virtual void CalcParams(double t = -1);  // Пересчет параметров
};

2. Сравнение структур хранения линейных и динамических структур данных.

Линейные структуры

Динамические структуры

Экзаменационный билет №24

1. Деревья поиска. Алгоритмы поиска и вставки.

FindRecord(TKey k, PTTreeNode pNode)
{
    if (pNode != NULL)
    {                       // лист
        if (pNode->Key < k) // вправо
            pNode = FindRecord(k, pNode->Right);
        if (pNode->Key > k) // влево
            pNode = FindRecord(k, pNode->Left);
    }
    return pNode;
}

Введение барьера.

FindRecord(TKey k, PTTreeNode pNode)
{
    if (pNode->Key < k) // вправо
        pNode = FindRecord(k, pNode->Right);
    if (pNode->Key > k) // влево
        pNode = FindRecord(k, pNode->Left);
    return (pNode == pBarrier) ? NULL : pNode;
}
void TTreeTable ::InsRecord(TKey k, PTDatValue pVal)
{ // вставить запись
    if (IsFull())
        SetRetCode(TabFull);
    else if (FindRecord(k) != NULL)
        SetRetCode(TabRecDbl);
    else
    {
        SetRetCode(TabOK);
        \*ppRef = new TTreeNode(k, pVal);
        DataCount++;
    }
}

2. Алгоритм копирования текста.

Экзаменационный билет №25

1. Алгоритм обхода плекса.

Алгоритм 1 - общая схема алгоритма обхода для плекса

while (pN (не принадлежит) TChartPoint)
{
    St.push(pN);
    pN = pN->GetFirstPoint();
}
//подъем по плексу и рисование
pF = pN;
while (!St.Empty())
{
    pN = St.top();
    St.Pop();
    pL = pN->GetLastPoint(); //рисование линии<pN, pF, pL>
    pF = pL;
}

Алгоритм 2 - рекурсивный вариант

TChartPoint *Show(TChart *pN)
{
    if (pN != NULL)
        pL = NULL;
    else if (pN (принадлежит) TChartPoint)
        pL = pN;
    else
    {
        pF = Show(pN->GetFirstPoint());
        pL = Show(pN->GetLastPoint()); //рисование линии <pN,pF,pL>
    }
    return pN;
}

2. Линейные структуры данных.

Линейные структуры данных - структуры, которым соответствует ориентированный граф с вершинами, лежащими на одной ломаной

Линейные структуры данных - упорядоченные структуры, в которых адрес элемента однозначно определяется его номером

Свойства:

Примеры линейных структур:

Экзаменационный билет №26

1. Таблицы с вычислимым входом. Запись и поиск при переполнении (способ открытого перемешивания).

Методичка с лабами.

Таблица – динамическая структура данных, базисным множеством которой является семейство линейных структур из записей.

Запись – кортеж, каждый элемент которого обычно именуется полем.

Имя записи (ключ) – одно из полей записи, по которому обычно осуществляется поиск записей в таблице; остальные поля образуют тело записи.

Хеш-функция – функция, ставящая в соответствие ключу номер записи в таблице.

Хеш-таблицами, таблицами с вычисляемыми адресами или перемешиваемыми таблицами называют таблицы, получаемые при некотором способе построения.

При использовании таблиц с вычисляемыми адресами может возникнуть ряд дополнительных проблем

Так, например, при вставке новой записи функция расстановки может выдать номер занятой строки массива (функция расстановки может определять одни и те же значения для нескольких разных ключей)

Метод открытого перемешивания (или закрытое хеширование) состоит в добавлении к вычисленному занятому номеру некоторого фиксированного смещения (поторное перемешивание) k' = (k + p) mod N

Среднее количество просматриваемых записей при поиске записи в перемешиваемых таблицах

Tср = (1 - a / 2) / (1 - a)

Следует отметить, что количество сравнений при поиске в перемешиваемых таблицах зависит не от количества записей в таблице, а от заполненности памяти, отведённой для размещения записей. Для примера, при заполненности массива на 75% (a = 0.75) количество сравнений в среднем равно 2.5.

Шпоры ПМИ

Функция преобразования значения ключа к номеру (адресу) строки памяти для хранения записи H: K → L (L = { 0, ... , M - 1 }) называется функцией расстановки (хеширования, перемешивания, рассеивания). Таблицы, представление которых организуется при использовании функции расстановки, называются таблицы с вычислимыми адресами (хеш-таблицы, перемешиваемые таблицы). При M < N (M - количество строк памяти, N - количество записей) функция расстановки является взаимно-неоднозначной (неинъективной). Темсымым, при использовании функции расстановки могут возникать ситуации, когда получаемый функцией номер строки памяти для расположения записи уже является использованным. Ситуация, когда для расположения записи функцией расстановки определяется уже занятая строка памяти, называется относительным переполнением (коллизией). Уменьшение эффекта сгущений может быть достигнуто при применении способа открытого или линейного перемешивания s' = (s + p) mod M (1 <= p < M). Возможное решение нахождения свободных строк состоит в выборе взаимнопростых значений для M и p. В более общем виде правило разрешения коллизии может быть представлено как функция вторичного перемешивания s' = h'(s).

Теорема: Алгоритм открытого перемешивания при взаимно-простых M и p гарантирует нахождение свободных строк структуры хранения таблицы.
Доказательство: Рассмотрим множество G = { 0, 1, ... , M - 1 } с операцией a ⊕ b = (a + b) mod M. Свойства операции: G замкнута относительно ⊕, операция ассоциативна и коммутативна, ∃ нулевой и обратные элементы => Множество G с операцией ⊕ является группой. Выделим подмножество G' = { 0, a, a ⊕ a, ... }. Такое множество G' с операцией ⊕ тоже является группой (такие группы называются циклическими). Обозначим a ⊕ a ⊕ ... ⊕ a через na (a - число повторений). Если n > 0, то минимальное значение n, при котором na = 0, называется порядком элемента a и обозначатся |a| (т.е. порядок определяет количество итераций открытого перемешивания, после которого начнётся повторение строк). Целое значение в операции (n a) / M получится только при n = M (т.к. a < M и для взаимно простых a и M). Но это означает также, что na = 0, и, тем самым, |a| = M. Отсюда следует G = G'.

При открытом перемешивании размер памяти для таблицы фиксирован + хранение записей без упорядоченности по ключам.

При разрешении коллизии просматриваемые строки могут рассматриваться как список, в котором порядок следования определяется при помощи алгоритмического правила. Тем самым, удаление записи в середине подобного списка не должно разрушать связность записей. Это может быть достигнуто специальной маркировкой строк с удалёнными записями. Строка структуры хранения имеет три возможных состояния - свободное, занятое, пустое (пустое состояние строки возникает посе удаления хранимой в строке записи).

Вставка:

1. Если n==M, ТО { Переполнение; Останов }
2. f = -1 // f – номер первой найденной пустой строки
3. s = h(key) // применение функции расстановки
4. ЕСЛИ s занята и K[s]==key, ТО {Дублир.; Останов }
5. ЕСЛИ s пустая и (f < 0), ТО { f = s }
6. ЕСЛИ s свободна и (f < 0), ТО { K[s]=key; Останов }
7. ЕСЛИ s свободна и (f >-1), ТО { K[f]=key; Останов }
8. (!) Коллизия {s = (s+p) mod M и переход к п. 4 }.

Поиск:

1) f = -1 // f – номер первой найденной пустой строки
2) s = h(key) // применение функции расстановки
3) ЕСЛИ s занята и K[s]==key, ТО { Останов }
4) ЕСЛИ s пустая и (f < 0), ТО { f = s }
5) ЕСЛИ s свободна, ТО { Останов }
6) (!) Коллизия { s = (s+p) mod M и переход к п. 3 }.

2. Понятие линейного списка.

Необходимость перепаковки для обеспечения динамического распределения памяти возникает в силу принятого способа реализации отношения следования - следующий элемент структуры располагается в следующем элементе памяти (с адресом, большим на 1). Устранение перепаковки возможно только при кардинальном изменении способа реализации основных отношений – необходимо допустить размещение следующих элементов структуры в произвольных элементах памяти (там, где имеется свободные области памяти). Возможность такого подхода может быть обеспечена запоминанием для каждого текущего элемента структуры адреса памяти, где хранится следующий элемент. Интерпретация содержимого элемента памяти (значение или адрес следующего элемента) в самом простом варианте может быть обеспечена фиксированным форматом используемых участков памяти.

Под квантом памяти понимается последовательность элементов памяти с последовательно-возрастающими адресами.

Именем (адресом) этой группы считается адрес первого слова кванта. Элементы кванта называются полями. В общем случае, набор элементов памяти, связанных с одним именем, называют звеном.

Далее будут использоваться двухэлементные звенья памяти, в которых первое поле будет использоваться для хранения значений, а второе поле – для запоминания адресов.

Способ задания отношения следования, в котором фиксация месторасположения следующего элемента производится путем запоминания соответствующего адреса памяти, называется сцеплением (пары, хранящие ai и ai+1, сцеплены адресными указателями).

Для изображения структуры хранения с использованием сцепления звенья памяти рисуются в виде прямоугольников, а сцепление звеньев показывается в виде стрелок.

Индикация последнего звена в списке обычно производится записью в поле адреса некоторого барьера – фиктивного (неадресного) значения (как правило, 0 или -1). Для доступа к звеньям списка должен быть известен адрес первого звена списка. Указатель, в котором этот адрес запоминается, называется переменной связи.

Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.

Экзаменационный билет №27

1. Таблицы с вычислимым входом. Метод цепочек для разрешения коллизий.

Копия билета 13.2

Методичка с лабами.

Таблица – динамическая структура данных, базисным множеством которой является семейство линейных структур из записей. Запись – кортеж, каждый элемент которого обычно именуется полем. Имя записи (ключ) – одно из полей записи, по которому обычно осуществляется поиск записей в таблице; остальные поля образуют тело записи. Хеш-функция – функция, ставящая в соответствие ключу номер записи в таблице.

Хеш-таблицами, таблицами с вычисляемыми адресами или перемешиваемыми таблицами называют таблицы, получаемые при некотором способе построения. Этот способ построения таблиц при большом количестве записей состоит в предварительном (перед непосредственным поиском по таблице) вычислении месторасположения искомой записи. Данный метод предполагает наличие некоторой простой функции h(key), которая отображает множество имен на множество номеров строк таблицы. Эта функция называется функцией хеширования или расстановки.
Эффективность обработки табиц с вычислимым входом зависит не от количества записей, а от степени заполненности структуры хранения.

При использовании таблиц с вычисляемыми адресами может возникнуть ряд дополнительных проблем. Так, например, при вставке новой записи функция расстановки может выдать номер занятой строки массива (функция расстановки может определять одни и те же значения для нескольких разных ключей). Такая ситуация называется относительным переполнением таблицы или коллизией. При возникновении коллизий возможны разные методы их разрешения. Рассмотрим метод цепочек.

Метод цепочек при возникновении коллизий формирует линейные списки (цепочки), в каждом из которых располагаются записи с одинаковым значением функции расстановки (в этом случае в строках массива для размещения записей следует добавить ещё одно поле для ссылки на следующее звено списка).

Шпоры ПМИ

Функция преобразования значения ключа к номеру (адресу) строки памяти для хранения записи H: K → L (L = { 0, ... , M - 1 }) называется функцией расстановки (хеширования, перемешивания, рассеивания). Таблицы, представление которых организуется при использовании функции расстановки, называются таблицы с вычислимыми адресами (хеш-таблицы, перемешиваемые таблицы). При M < N (M - количество строк памяти, N - количество записей) функция расстановки является взаимно-неоднозначной (неинъективной). Темсымым, при использовании функции расстановки могут возникать ситуации, когда получаемый функцией номер строки памяти для расположения записи уже является использованным. Ситуация, когда для расположения записи функцией расстановки определяется уже занятая строка памяти, называется относительным переполнением (коллизией).

Метод цепочек (или открытое хеширование) - все записи, для которых функция хеширования определяет одно и тоже значение, представляются в виде линейного списка.
Метод цепочек обеспечивает получение структуры хранения таблицы с динамическим распределением памяти.

Википедия

Каждая ячейка массива является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента. Операции поиска или удаления элемента требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления элемента нужно добавить элемент в конец или начало соответствующего списка, и, в случае, если коэффициент заполнения станет слишком велик, увеличить размер массива и перестроить таблицу.

2. Плекс, как представление арифметического выражения.

Копия билета 2.2

Плекс может рассматриваться как структура представления для выражений самого общего вида (линия – операция, точки - операнды).

Пример: Арифметическое выражение (a * b + c) * (d - e / f):

Экзаменационный билет №28

1.Сравнительная характеристика способов организации таблиц

НЕТУ ЧОТА

2. Представление текста связным списком.

Экзаменационный билет №29

1.Структура хранения множеств.

Множество – набор элементов.

Для множества определены операции:

Проектирование:

2. Повторное использование памяти (сборка мусора).

При удалении разделов текста для освобождения звеньев следует учитывать следующие моменты:

Память, занимаемая удаляемым текстом, не освобождается, а удаление текста фиксируется установкой указателей в состояние NULL (например, pFirst=NULL). Подобный способ выполнения операций удаления текста может привести к ситуации, когда в памяти, используемой для хранения текста, могут присутствовать звенья, на которые нет ссылок в тексте и которые не возвращены в систему управления памятью для повторного использования. Элементы памяти такого вида носят наименование "мусора". Наличие "мусора" в системе может быть допустимым, если имеющейся свободой памяти достаточно для работы программ. В случае нехватки памяти необходимо выполнить "сборку мусора".

Возможный подход доступа к системе управления памятью – разработка специальной системы управления при помощи перегрузки операторов new и delete.

Общая схема подхода:

class TTextMem{
    PTTextLink pFirst; // первое звено
    PTTextLink pLast; // последнее звено
    PTTextLink pFree; // первое свободное
void TTextLink::InitMemSystem(int size) // инициализация памяти
{
    char Line[100];
    char *tmp = new char[sizeof(TTextLink)*size];
    MemHeader.pFirst = (PTTextLink)new char[sizeof(TTextLink)*size];
    MemHeader.pFree = MemHeader.pFirst;
    MemHeader.pLast = (PTTextLink)tmp + size - 1;
    PTTextLink pLink = MemHeader.pFirst;
    for (int i = 0; i < size - 1; i++, pLink++) // размер памяти
        pLink->pNext = pLink + 1;
    pLink->pNext = nullptr;
}
void * TTextLink::operator new(size_t size) // выделение звена
{
    PTTextLink pLink = MemHeader.pFree;
    if (MemHeader.pFree != nullptr)
        MemHeader.pFree = pLink->pNext;
    return pLink;
}
void operator delete (void *pM)
{
    PTTTextLink pLink=(PTTTextLink)pM;
    pLink->pNext=MemHeader.pFree;
    MemHeader.pFree=pLink;
}

Экзаменационный билет №30

1.Группирование геометрических объектов

Составной объект - набор геометрических объектов (как базовых так и составных), рассматриваемых при выполнении операций обработки как единый объект

class TChartGroup : public TChartRoot
{
 protected:
    TDatList Group;  // Список объектов
 public:
    TChartGroup() { }
    void InsUnit(TChartRoot *pUnit);  // Добавление
    virtual void Show();  // Визуализация
    virtual void Hide();  // Скрытие
    virtual void CalcParams(double t = -1);  // Пересчет параметров
};

2. Алгоритмы обхода графов. Поиск в глубину.

Экзаменационный билет №31

1.Конструирование геометрических объектов.

Геометрический объект может быть сконструирован с использованием уже существующих объектов

class TChartPolyline : public TChartGroup
{
 public:
    TChartPolyline() { }
    void InsPoint(TChartRoot *pUnit);  // Добавление
    virtual void Show();  // Визуализация
    virtual void Hide();  // Скрытие
    virtual void CalcParams(double t = -1);  // Пересчет параметров
};

2. Алгоритмы обхода графов. Поиск в ширину.

Экзаменационный билет №32

1.Комбинирование геометрических объектов (плексы).

Геометрический объект может быть образован при помощи сборки существующих объектов.

Рассмотрим данный способ построения новых объектов на примере рисунков (чертежей), образованных только их объектов двух базовых типов: точек и линий

Алгоритм 1 - общая схема алгоритма обхода для плекса

while (pN (не принадлежит) TChartPoint)
{
    St.push(pN);
    pN = pN->GetFirstPoint();
}
//подъем по плексу и рисование
pF = pN;
while (!St.Empty())
{
    pN = St.top();
    St.Pop();
    pL = pN->GetLastPoint(); //рисование линии<pN, pF, pL>
    pF = pL;
}

Алгоритм 2 - рекурсивный вариант

TChartPoint *Show(TChart *pN)
{
    if (pN != NULL)
        pL = NULL;
    else if (pN (принадлежит) TChartPoint)
        pL = pN;
    else
    {
        pF = Show(pN->GetFirstPoint());
        pL = Show(pN->GetLastPoint()); //рисование линии <pN,pF,pL>
    }
    return pN;
}

ДОБАВИТЬ ПИКЧИ

2. Реализация алгоритма обхода графа.

Алгоритмы обхода (итератор)

TSearchMode; // способ обхода
PTGraphNode pCurrNode; // текущая вершина
// Достигнутые, но не обработанные вершины
TDataRoot *pStream;
// Множество вершин, достигнутых в ходе обхода
TBitField *pFound;

Инициализация (Reset)

Проверка завершения (IsGraphEnded)

return pCurrNode == NULL // тукущее звено?

Переход к следующей вершине графа (GoNext)

    int Reset (void); // установить на первую вершину
    int IsGraphEnded (void) const; // обход завершен?
    int GoNext (void); // переход к следующей вершине
    PTGraphNode GetCurrNode (void) { return pCurrNode; } // доступ
    PTGraphPath GetShortestPath (string fn, string ln); // поиск кратчайшего пути
protected:
    virtual void Print (ostream &os); // печать графа
};
typedef TGraph * PTGraph;
// end of tgraph.h